package com.gxc.linkedList;

public class Sort {

    public static void main(String[] args) {
        Node head = Loopback.createNode();

        int pivot = 4;
        head = sort(head, pivot);

        while (head!=null) {
            System.out.println(head.value);
            head = head.next;
        }
    }

    /**
     * 把小于pivot的放左边，等于的放中间，大于的放右边
     * @param head
     * @param pivot
     * @return
     */
    private static Node sort(Node head, int pivot) {
        //小于的链表
        Node lHead=null;
        Node ltail=null;
        //等于的链表
        Node eHead=null;
        Node etail=null;
        //大于的链表
        Node rHead=null;
        Node rtail=null;

        Node cur = head;
        Node next;
        while (cur!=null) {
            next = cur;
            if (cur.value<pivot) {
                if (lHead == null) lHead = cur;
                if (ltail != null) ltail.next = cur;
                ltail = cur;
            } else if (cur.value == pivot) {
                if (eHead == null) eHead = cur;
                if (etail != null) etail.next = cur;
                etail = cur;
            } else {
                if (rHead == null) rHead = cur;
                if (rtail != null) rtail.next = cur;
                rtail = cur;
            }
            cur = cur.next;
            next.next = null;
        }

        //三个链表头尾相连
        Node nodeHead=null;
        Node nodeTial=null;
        if (lHead != null) {
            nodeHead = lHead;
            nodeTial = ltail;
        }
        if (eHead!=null) {
            if (nodeHead == null) {
                nodeHead = eHead;
                nodeTial = etail;
            } else {
                nodeTial.next = eHead;
                nodeTial = etail;
            }
        }
        if (rHead!=null) {
            if (nodeHead == null) {
                nodeHead = rHead;
                nodeTial = rtail;
            } else {
                nodeTial.next = rHead;
                nodeTial = rtail;
            }
        }
        return nodeHead;
    }


}
